The Discrete Cosine Transform ("DCT") is well known to those skilled in the art. In some applications, for example image compression (the reduction of the amount of storage necessary to hold an image ), the Discrete Cosine Transform is extensively used. The DCT represents an input sequence of N real numbers as a weighted sum of N distinct cosine curves. Each of these N cosine curves has a different frequency (the number of times the curve completes a cycle from 1 through 0, -1, 0 and back to 1 as the independent variable ranges from 0 to N). The output of a DCT is the collection of these N weights.
The DCT represents the input sequence as a weighted sum of periodic curves; the word "periodic" means that, after a certain real number p (the period), the values repeat so that the value at position p is the same as the value at the initial position O, and in general the value at position p+x is the same as the value at position x. Thus the DCT assumes that the input sequence of N real numbers is a part of an infinite periodic sequence of real numbers.
The DCT differs from the Discrete Fourier Transform, the most popular data sequence transformation technology, in the way in which the input sequence of N real numbers is a part of the infinite periodic sequence of real numbers.
The Discrete Fourier Transform("DFT") is a widely used signal processing and analysis concept; and sophisticated signal processing systems have been developed based upon its features. DFT devices are used in a great variety of fields such as, e.g., applied mechanics, sonics and acoustics, biomedical engineering, signal processing, instrumentation, radar, electromagnetics, communications, and the like. See, for example, pages 1-3 of E. Oran Brigham's "The Fast Fourier Transform and its Applications" (Prentice Hall, Englewood Cliffs, N.J., 1988).
One of the most important uses of transform technology is "filtering." Some applications of filtering are image enhancement, target detection in radar, refocusing, and image compression. The process of "filtering" is achieved by transforming a given input sequence, either with the DCT or DFT or perhaps some other Fourier type transform, modifying the transformed sequence, and then performing an inverse transform on the modified transformed sequence.
To use the DFT or the DCT, one must regard the input sequence of N real numbers as embedded in an infinite periodic sequence of real numbers of period equal to N or 2N respectively. This "extended" periodic sequence is obtained in a natural way by cycling through the N point sequence over and over in both directions. For example, if N=4 and the 4 point sequence consists of the 4 numbers 0 1 2 and 3, then we may symbolically represent the extended input sequence for a DFT by:
______________________________________ data values 0 1 2 3 0 1 2 3 0 1 2 3 indices -4 -3 -2 -1 0 1 2 3 4 5 6 7 ______________________________________
and we may symbolically represent the extended input sequence for a DCT by:
__________________________________________________________________________ data values 0 1 2 3 3 2 1 0 0 1 2 3 3 2 1 0 indices -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 __________________________________________________________________________
Note the data values corresponding to the zeroth and -1st indices of the extended DFT input sequence above (which from this point on may be referred to as the zeroth and -1st values of the extended DFT input sequence) and the data values corresponding to the zeroth and -1st indices of the extended DCT input sequence above (which from this point on may be referred to as the zeroth and -1st values of the extended DCT input sequence). In the DCT, the value of the zeroth element is automatically equal to the value of the -1st element. However, in the DFT, the zeroth element has a value of 0 and the -1st element has a value of 3 (These two values are not equal). Either extended input sequence is transformed appropriately, then filtered, and then inverse transformed. In the following discussion, this shall be referred to as the "filtered sequence". Typically the value of the kth element of this filtered sequence depends on values of elements of the corresponding extended input sequence near its kth element. Consequently, in the case of, for example, the DFT above, the value of the zeroth element of the filtered sequence depends on both the value of the zeroth element of G the input sequence and the value of the -1st element of the input sequence. But the value of the -1st element of the input sequence is equal to the value of the 3rd ( the last ) element of the input sequence. So the values of both endpoints of the original four point sequence significantly contribute to the value of the zeroth element of the filtered output sequence.
This anomaly does not happen for the DCT. For the extended DCT input sequence above, the value of the -1st element is by its very construction equal to the value of the zeroth element. So the value of the 3rd element (the last) does not significantly contribute to the value of the zeroth element of the filtered output.
Summarizing the above discussion, when filtering with the DCT the kth output depends on elements of the input sequence with indices near k. But in a DFT filtered output sequence the first elements will depend significantly on the last elements of the input sequence (likewise, the last elements of the filtered output sequence will depend significantly on the first elements of the input sequence). When the beginning and end of the input sequence differ significantly in value, the DFT filtered output will be distorted by this effect but the DCT filtered output will not suffer.
For the reasons specified above, the cosine transform is superior to the Fourier transform in many applications, such as image processing, image compression, and the like.
It is an object of this invention to provide a device for utilizing a discrete Fourier transformer to implement a discrete cosine transformer.
It is another object of this invention to provide a device for transforming a real input signal whose number of data points is not necessarily equal to a power of 2.
It is another object of this invention to provide a device for transforming two real discrete input signals simultaneously into their respective discrete cosine transforms.
It is another object of this invention to provide a device for utilizing a discrete Fourier transformer to implement a discrete cosine transformer which is adaptable to be used in any known discrete Fourier transform apparatus.
It is another object of this invention to provide a device for utilizing a discrete Fourier transformer to implement a discrete cosine transformer which devices operates at an extremely fast speed.
It is another object of this invention to provide a device suitable for utilizing a one-dimensional, discrete Fourier transformer to implement an efficient two- or three-dimensional cosine transformer.
It is another object of this invention to provide a relatively inexpensive device for utilizing a discrete Fourier transformer to implement a discrete cosine transformer.